package com.hy.treeNode3;

import com.hy.treeNode.TreeNode;

import java.util.List;

public class HasPathSum {

    /**
     * 0112.路径总和
     * @param root
     * @param targetSum
     * @return
     */
    // 解法1
    public boolean hasPathSum(TreeNode root,int targetSum){
        if (root == null){
            return false;
        }
        targetSum -= root.val;
        if (root.left == null && root.right == null){
            return targetSum == 0;
        }

        if (root.left != null){
            boolean flag = hasPathSum(root.left, targetSum);
            if (flag){
                return true;
            }
        }
        if (root.right != null){
            boolean flag = hasPathSum(root.right, targetSum);
            if (flag){
                return true;
            }
        }
        return false;
    }

    // 解法2
    public boolean hasPathSum2(TreeNode root,int targetSum){
        if (root == null){
            return false;
        }
        // 叶子节点判断是否符合
        if (root.left == null && root.right == null){
            return targetSum == root.val;
        }
        // 求两侧分支的路径和
        return hasPathSum2(root.left,targetSum - root.val) || hasPathSum2(root.right,targetSum - root.val);
    }

    public static void main(String[] args) {
        TreeNode leftNode1 = new TreeNode(1, null, null);
        TreeNode rightNode1 = new TreeNode(2, null, null);

        TreeNode leftNode2 = new TreeNode(6, null, null);
        TreeNode rightNode2 = new TreeNode(8, null, null);

        TreeNode leftNode = new TreeNode(4, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(7, leftNode2, rightNode2);

        TreeNode root = new TreeNode(5, leftNode, rightNode);

        HasPathSum hasPathSum = new HasPathSum();

        System.out.println("路径总和-i: "+hasPathSum.hasPathSum(root,18));
        System.out.println("路径总和-ii: "+hasPathSum.hasPathSum2(root,18));
    }
}
